import java.util.Scanner;

/**
 *  正数序列
 */
public class test24 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        int a1 = 2;
        int a2 = 2;
        int a3 = 3;
        int a4 = 0;
        if(num == 1)
            System.out.println(a1);
        if(num == 2)
            System.out.println(a2);
        if(num == 3)
            System.out.println(a3);
        for (int i = 4; i <= num ; i++) {
            a4 = (a1+a2+a3)%10000;
            a1 = a2;
            a2 = a3;
            a3 =a4;
        }
        if(num>=4)
            System.out.println(a4);
    }
}
